{
 "cells": [
  {
   "cell_type": "markdown",
   "id": "51774423-ce32-409a-bbb5-f919441148ba",
   "metadata": {},
   "source": [
    "# <center>操作系统内存分配实验</center>\n",
    "### <center>邓永盛  2021.2.7</center>"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "729d7fb4-2527-4b21-9388-45f3e38fc81e",
   "metadata": {},
   "source": [
    "## 1.1 未分配内存区块对象定义"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "id": "fbc3dae6-383d-4d7a-8942-6c35a03f7d23",
   "metadata": {},
   "outputs": [],
   "source": [
    "class unused:\n",
    "    \"\"\"\n",
    "    未使用的内存区块对象\n",
    "    \"\"\"\n",
    "    start = int()\n",
    "    end = int()\n",
    "    size = int()\n",
    "    \n",
    "    def __init__(self,start:int,end:int=None,size:int=None):\n",
    "        \"\"\"\n",
    "        创建一个未分配内存区块对象，end和size必须指定其一\n",
    "        start: 起始地址\n",
    "        end: 区块结束地址\n",
    "        size: 区块大小\n",
    "        \"\"\"\n",
    "        self.start = start\n",
    "        if end==None:\n",
    "            self.end = start + size\n",
    "            self.size = size\n",
    "        elif size==None:\n",
    "            self.end = end\n",
    "            self.size = end - start\n",
    "        else:\n",
    "            raise RuntimeError('end，size参数必须指定其一')\n",
    "            \n",
    "    def __repr__(self):\n",
    "        return \"(空闲区)\\t\\t 起始地址:0x%04x\\t 结束地址:0x%04x\\t 空间大小:0x%04x\\n\"%(self.start,self.end,self.size)\n",
    "    \n",
    "    def __str__(self):\n",
    "        return self.__repr__()\n",
    "    \n",
    "    def allocate(self,allosize:int,process:str):\n",
    "        print(\"从空闲区中分配一块0x%04x的空间\"%allosize)\n",
    "        if allosize < self.size:\n",
    "            #从头部分配空间\n",
    "            self.start += allosize\n",
    "            self.size -= allosize\n",
    "            print(\"分配成功\")\n",
    "            return used(start=self.start-allosize,process=process,size=allosize)\n",
    "        else:\n",
    "            print(\"该区块空间不足以分配\")"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "2292b00d-066a-4337-b790-c81d9a6f871b",
   "metadata": {},
   "source": [
    "## 1.2 已分配内存区块对象定义"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "id": "330a7914-f467-4fd4-bf98-aa6084ddc6a1",
   "metadata": {},
   "outputs": [],
   "source": [
    "class used:\n",
    "    \"\"\"\n",
    "    已分配的内存区块对象\n",
    "    \"\"\"\n",
    "    start = int()\n",
    "    end = int()\n",
    "    size = int()\n",
    "    process = str()\n",
    "\n",
    "    def __init__(self,process:str,start:int,end:int=None,size:int=None):\n",
    "        \"\"\"\n",
    "        创建一个已分配内存区块对象，end和size必须指定其一\n",
    "        process: 进程名\n",
    "        start: 起始地址\n",
    "        end: 区块结束地址\n",
    "        size: 区块大小\n",
    "        \"\"\"\n",
    "        self.start = start\n",
    "        self.process = process\n",
    "        if end==None:\n",
    "            self.end = start + size\n",
    "            self.size = size\n",
    "        elif size==None:\n",
    "            self.end = end\n",
    "            self.size = end - start\n",
    "        else:\n",
    "            raise RuntimeError('end，size参数必须指定其一')\n",
    "            \n",
    "    def __repr__(self):\n",
    "        return \"(已分配区)\\t 起始地址:0x%04x\\t 结束地址:0x%04x\\t 空间大小:0x%04x\\t 占用进程:%s\\n\"%(self.start,self.end,self.size,self.process)\n",
    "    \n",
    "    def __str__(self):\n",
    "        return self.__repr__()\n",
    "    \n",
    "    def free(self):\n",
    "        \"\"\"\n",
    "        释放此区块占用的空间，释放成功后返回一个unused对象\n",
    "        \"\"\"\n",
    "        un = unused(self.start,size=self.size)\n",
    "        print(\"成功回收 %s 占用的 %d 内存\"%(self.process,self.size))\n",
    "        self.size=0\n",
    "        self.end=self.start\n",
    "        return un"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "d6a965ce-5301-4234-838e-5370555b1311",
   "metadata": {},
   "source": [
    "## 1.3 内存对象定义"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "id": "a7ef1fb3-18ff-46ac-85a9-23618ac900fe",
   "metadata": {},
   "outputs": [],
   "source": [
    "class memory:\n",
    "    \"\"\"\n",
    "    内存对象\n",
    "    \"\"\"\n",
    "    size = int()\n",
    "    freelist = list()\n",
    "    usedlist = list()\n",
    "    \n",
    "    def __init__(self,memorysize:int=0x10000):\n",
    "        \"\"\"创建一个内存总大小为memorysize的内存对象\"\"\"\n",
    "        self.size = memorysize\n",
    "        self.freelist.append(unused(start=0,size=memorysize))\n",
    "        \n",
    "    def __repr__(self):\n",
    "        return \"总大小:0x%04x\\t 已分配: 0x%04x\\t 未分配: 0x%04x\\n空闲区:\\n%s已分配区:\\n%s\"%(self.size,self.info()['usedsize'],self.info()['freesize'],\"\".join(map(str,self.freelist)),\"\".join(map(str,self.usedlist)))\n",
    "        \n",
    "    def __str__(self):\n",
    "        return self.__repr__()\n",
    "    \n",
    "    def allocate(self,process:str,allosize:int,algorithm=\"FF\"):\n",
    "        \"\"\"\n",
    "        从内存中分配allosize大小的连续内存空间\n",
    "        process: 进程名\n",
    "        allosize: 需要的空间大小\n",
    "        \"\"\"\n",
    "        if len(list(filter(lambda x: x.size >= allosize,self.freelist))) < 1:\n",
    "            raise RuntimeError(\"没有空间大小超过 0x%04x 的连续区块，无法为进程 %s 分配内存空间\"%(allosize,process))\n",
    "        if algorithm == \"FF\":\n",
    "            for freemem in filter(lambda x: x.size >= allosize,self.freelist):\n",
    "                    self.usedlist.append(freemem.allocate(allosize,process))\n",
    "                    self.collect()\n",
    "                    break\n",
    "        elif algorithm == \"NF\":\n",
    "            pass\n",
    "        elif algorithm == \"BF\":\n",
    "            pass\n",
    "        elif algorithm == \"WF\":\n",
    "            pass\n",
    "        else:\n",
    "            raise RuntimeError(\"指定的算法错误\")\n",
    "    \n",
    "    def terminate(self,process:str):\n",
    "        \"\"\"结束进程，释放其占用的全部内存\"\"\"\n",
    "        print(\"结束进程 %s\"%process)\n",
    "        for usedmem in filter(lambda x: x.process==process, self.usedlist):\n",
    "            self.freelist.append(usedmem.free())\n",
    "        self.collect()\n",
    "    \n",
    "    def collect(self):\n",
    "        \"\"\"内存整理函数，删除size为0的区块，合并相邻的空闲区块\"\"\"\n",
    "        #删除size==0的区块\n",
    "        self.freelist = list(filter(lambda x:x.size>0,self.freelist))\n",
    "        self.usedlist = list(filter(lambda x:x.size>0,self.usedlist))\n",
    "        #合并相邻的空闲区块\n",
    "        for mem1 in self.freelist:\n",
    "            for mem2 in self.freelist:\n",
    "                if mem1 is mem2:\n",
    "                    continue\n",
    "                if mem1.end == mem2.start:\n",
    "                    mem1.end = mem2.end\n",
    "                    mem1.size += mem2.size\n",
    "                    self.freelist.remove(mem2)\n",
    "        #将内存区块按照地址排序\n",
    "        self.freelist.sort(key=lambda x: x.start)\n",
    "        self.usedlist.sort(key=lambda x: x.start)\n",
    "    \n",
    "    def info(self):\n",
    "        \"\"\"获取内存的分配情况信息\"\"\"\n",
    "        freesize = sum(map(lambda x: x.size,self.freelist))\n",
    "        usedsize = sum(map(lambda x: x.size,self.usedlist))\n",
    "        return {'freesize':freesize,'usedsize':usedsize}"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "de8578f0-0607-4a12-86a2-ff803d895aa9",
   "metadata": {},
   "source": [
    "## 2.1 创建一个内存对象"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "id": "89660f13-5403-4b14-9568-6638282a65f6",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "总大小:0x10000\t 已分配: 0x0000\t 未分配: 0x10000\n",
       "空闲区:\n",
       "(空闲区)\t\t 起始地址:0x0000\t 结束地址:0x10000\t 空间大小:0x10000\n",
       "已分配区:"
      ]
     },
     "execution_count": 4,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "mem = memory()\n",
    "mem"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "aa2cee10-2bf9-4aa4-a6c4-76e0d1aa0855",
   "metadata": {},
   "source": [
    "## 2.2 为进程p1分配0x100的内存"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "id": "1961adbf-ad0b-4d86-9e4d-6ca021dbf250",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "从空闲区中分配一块0x0100的空间\n",
      "分配成功\n"
     ]
    },
    {
     "data": {
      "text/plain": [
       "总大小:0x10000\t 已分配: 0x0100\t 未分配: 0xff00\n",
       "空闲区:\n",
       "(空闲区)\t\t 起始地址:0x0100\t 结束地址:0x10000\t 空间大小:0xff00\n",
       "已分配区:\n",
       "(已分配区)\t 起始地址:0x0000\t 结束地址:0x0100\t 空间大小:0x0100\t 占用进程:p1"
      ]
     },
     "execution_count": 5,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "mem.allocate(\"p1\",0x100)\n",
    "mem"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "f435be40-ea70-4375-8cca-eab15bfa13d2",
   "metadata": {},
   "source": [
    "## 2.3 为进程p2分配0x200的内存"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "id": "d093e987-d0bc-4f6b-8465-e55f388fe9b4",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "从空闲区中分配一块0x0200的空间\n",
      "分配成功\n"
     ]
    },
    {
     "data": {
      "text/plain": [
       "总大小:0x10000\t 已分配: 0x0300\t 未分配: 0xfd00\n",
       "空闲区:\n",
       "(空闲区)\t\t 起始地址:0x0300\t 结束地址:0x10000\t 空间大小:0xfd00\n",
       "已分配区:\n",
       "(已分配区)\t 起始地址:0x0000\t 结束地址:0x0100\t 空间大小:0x0100\t 占用进程:p1\n",
       "(已分配区)\t 起始地址:0x0100\t 结束地址:0x0300\t 空间大小:0x0200\t 占用进程:p2"
      ]
     },
     "execution_count": 6,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "mem.allocate(\"p2\",0x200)\n",
    "mem"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "05c48c1d-b2c3-4d72-86b8-c8ae1274d68c",
   "metadata": {},
   "source": [
    "## 2.4 为进程p1再分配0x100的内存"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "id": "8ae93bef-2afd-42ee-a595-c005bae646a0",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "从空闲区中分配一块0x0100的空间\n",
      "分配成功\n"
     ]
    },
    {
     "data": {
      "text/plain": [
       "总大小:0x10000\t 已分配: 0x0400\t 未分配: 0xfc00\n",
       "空闲区:\n",
       "(空闲区)\t\t 起始地址:0x0400\t 结束地址:0x10000\t 空间大小:0xfc00\n",
       "已分配区:\n",
       "(已分配区)\t 起始地址:0x0000\t 结束地址:0x0100\t 空间大小:0x0100\t 占用进程:p1\n",
       "(已分配区)\t 起始地址:0x0100\t 结束地址:0x0300\t 空间大小:0x0200\t 占用进程:p2\n",
       "(已分配区)\t 起始地址:0x0300\t 结束地址:0x0400\t 空间大小:0x0100\t 占用进程:p1"
      ]
     },
     "execution_count": 7,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "mem.allocate(\"p1\",0x100)\n",
    "mem"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "5f94ed5e-b4f7-4fdc-ab50-a2cf988ab93d",
   "metadata": {},
   "source": [
    "## 2.5 结束进程p1，释放它占用的所有内存空间"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "id": "90534d76-74e4-4d05-ab0c-06a56a649c46",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "结束进程 p1\n",
      "成功回收 p1 占用的 256 内存\n",
      "成功回收 p1 占用的 256 内存\n"
     ]
    },
    {
     "data": {
      "text/plain": [
       "总大小:0x10000\t 已分配: 0x0200\t 未分配: 0xfe00\n",
       "空闲区:\n",
       "(空闲区)\t\t 起始地址:0x0000\t 结束地址:0x0100\t 空间大小:0x0100\n",
       "(空闲区)\t\t 起始地址:0x0300\t 结束地址:0x10000\t 空间大小:0xfd00\n",
       "已分配区:\n",
       "(已分配区)\t 起始地址:0x0100\t 结束地址:0x0300\t 空间大小:0x0200\t 占用进程:p2"
      ]
     },
     "execution_count": 8,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "mem.terminate(\"p1\")\n",
    "mem"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "8aacf8a4-6f04-4404-92da-ce81b401cf85",
   "metadata": {},
   "source": [
    "## 2.6 为p3进程分配无法满足的空间大小\n",
    "这里会按照预期计划报错"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 9,
   "id": "78236366-0871-4648-9b72-19aa6137019b",
   "metadata": {},
   "outputs": [
    {
     "ename": "RuntimeError",
     "evalue": "没有空间大小超过 0x10000 的连续区块，无法为进程 p3 分配内存空间",
     "output_type": "error",
     "traceback": [
      "\u001b[1;31m---------------------------------------------------------------------------\u001b[0m",
      "\u001b[1;31mRuntimeError\u001b[0m                              Traceback (most recent call last)",
      "\u001b[1;32m<ipython-input-9-5a3d665fcc79>\u001b[0m in \u001b[0;36m<module>\u001b[1;34m\u001b[0m\n\u001b[1;32m----> 1\u001b[1;33m \u001b[0mmem\u001b[0m\u001b[1;33m.\u001b[0m\u001b[0mallocate\u001b[0m\u001b[1;33m(\u001b[0m\u001b[1;34m\"p3\"\u001b[0m\u001b[1;33m,\u001b[0m\u001b[1;36m0x10000\u001b[0m\u001b[1;33m)\u001b[0m\u001b[1;33m\u001b[0m\u001b[1;33m\u001b[0m\u001b[0m\n\u001b[0m",
      "\u001b[1;32m<ipython-input-3-8d9b240af1ba>\u001b[0m in \u001b[0;36mallocate\u001b[1;34m(self, process, allosize, algorithm)\u001b[0m\n\u001b[0;32m     25\u001b[0m         \"\"\"\n\u001b[0;32m     26\u001b[0m         \u001b[1;32mif\u001b[0m \u001b[0mlen\u001b[0m\u001b[1;33m(\u001b[0m\u001b[0mlist\u001b[0m\u001b[1;33m(\u001b[0m\u001b[0mfilter\u001b[0m\u001b[1;33m(\u001b[0m\u001b[1;32mlambda\u001b[0m \u001b[0mx\u001b[0m\u001b[1;33m:\u001b[0m \u001b[0mx\u001b[0m\u001b[1;33m.\u001b[0m\u001b[0msize\u001b[0m \u001b[1;33m>=\u001b[0m \u001b[0mallosize\u001b[0m\u001b[1;33m,\u001b[0m\u001b[0mself\u001b[0m\u001b[1;33m.\u001b[0m\u001b[0mfreelist\u001b[0m\u001b[1;33m)\u001b[0m\u001b[1;33m)\u001b[0m\u001b[1;33m)\u001b[0m \u001b[1;33m<\u001b[0m \u001b[1;36m1\u001b[0m\u001b[1;33m:\u001b[0m\u001b[1;33m\u001b[0m\u001b[1;33m\u001b[0m\u001b[0m\n\u001b[1;32m---> 27\u001b[1;33m             \u001b[1;32mraise\u001b[0m \u001b[0mRuntimeError\u001b[0m\u001b[1;33m(\u001b[0m\u001b[1;34m\"没有空间大小超过 0x%04x 的连续区块，无法为进程 %s 分配内存空间\"\u001b[0m\u001b[1;33m%\u001b[0m\u001b[1;33m(\u001b[0m\u001b[0mallosize\u001b[0m\u001b[1;33m,\u001b[0m\u001b[0mprocess\u001b[0m\u001b[1;33m)\u001b[0m\u001b[1;33m)\u001b[0m\u001b[1;33m\u001b[0m\u001b[1;33m\u001b[0m\u001b[0m\n\u001b[0m\u001b[0;32m     28\u001b[0m         \u001b[1;32mif\u001b[0m \u001b[0malgorithm\u001b[0m \u001b[1;33m==\u001b[0m \u001b[1;34m\"FF\"\u001b[0m\u001b[1;33m:\u001b[0m\u001b[1;33m\u001b[0m\u001b[1;33m\u001b[0m\u001b[0m\n\u001b[0;32m     29\u001b[0m             \u001b[1;32mfor\u001b[0m \u001b[0mfreemem\u001b[0m \u001b[1;32min\u001b[0m \u001b[0mfilter\u001b[0m\u001b[1;33m(\u001b[0m\u001b[1;32mlambda\u001b[0m \u001b[0mx\u001b[0m\u001b[1;33m:\u001b[0m \u001b[0mx\u001b[0m\u001b[1;33m.\u001b[0m\u001b[0msize\u001b[0m \u001b[1;33m>=\u001b[0m \u001b[0mallosize\u001b[0m\u001b[1;33m,\u001b[0m\u001b[0mself\u001b[0m\u001b[1;33m.\u001b[0m\u001b[0mfreelist\u001b[0m\u001b[1;33m)\u001b[0m\u001b[1;33m:\u001b[0m\u001b[1;33m\u001b[0m\u001b[1;33m\u001b[0m\u001b[0m\n",
      "\u001b[1;31mRuntimeError\u001b[0m: 没有空间大小超过 0x10000 的连续区块，无法为进程 p3 分配内存空间"
     ]
    }
   ],
   "source": [
    "mem.allocate(\"p3\",0x10000)"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.8.6"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 5
}
